//
// Created by 123 on 2024/3/14.
//
#include <iostream>

using namespace std;
typedef struct ThreadNode {
    int data;
    ThreadNode *lchild, *rchild;
//    为0 是孩子， 为1是线索
    int ltag, rtag;
} ThreadNode, *ThreadTree;

//初始化
ThreadNode *initThreadNode() {
    ThreadNode *node = (ThreadNode *) malloc(sizeof(ThreadNode));
    node->lchild = NULL;
    node->rchild = NULL;
    node->ltag = 0;
    node->rtag = 0;
    return node;
}

//构造中序线索化二叉树
void crerateThreadTree(ThreadTree &node);

//构造中序线索化二叉树  构造细节
void inThreadTree(ThreadTree &node, ThreadTree &pre);


//求中序线索化二叉树的中序序列下的第一个结点
ThreadNode *firstNode(ThreadTree tree);

//求中序线索化二叉树中结点p在中序序列下的后继结点
ThreadNode *nextNode(ThreadNode *node);

//求中序线索化二叉树中的中序遍历算法
void inOrder(ThreadTree tree);


//遍历到该节点的操作
void visit(ThreadNode *node);


int main() {
    ThreadTree tree = initThreadNode();
    tree->data = 1;
    ThreadNode *n2 = initThreadNode();
    n2->data = 2;
    ThreadNode *n3 = initThreadNode();
    n3->data = 3;
    ThreadNode *n4 = initThreadNode();
    n4->data = 4;
    ThreadNode *n5 = initThreadNode();
    n5->data = 5;
    ThreadNode *n6 = initThreadNode();
    n6->data = 6;
    ThreadNode *n7 = initThreadNode();
    n7->data = 7;
    ThreadNode *n8 = initThreadNode();
    n8->data = 8;
    ThreadNode *n9 = initThreadNode();
    n9->data = 9;

    tree->lchild = n2;
    tree->rchild = n3;

    n2->lchild = n4;
    n2->rchild = n5;

    n3->lchild = n6;
    n3->rchild = n7;

    n4->lchild = n8;
    n4->rchild = n9;

    crerateThreadTree(tree);
    inOrder(tree);


}

void visit(ThreadNode *node) {
    cout << node->data << "   ";
}

//构造中序线索化二叉树
void crerateThreadTree(ThreadTree &node) {
    ThreadTree pre = NULL;
    if (node != NULL) {
        inThreadTree(node, pre);
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}

//构造中序线索化二叉树  构造细节
void inThreadTree(ThreadTree &node, ThreadTree &pre) {
    if (node != NULL) {
        inThreadTree(node->lchild, pre);
        if (node->lchild == NULL) {
            node->lchild = pre;
            node->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = node;
            pre->rtag = 1;
        }
        pre = node;
        inThreadTree(node->rchild, pre);
    }
}

//求中序线索化二叉树的中序序列下的第一个结点
ThreadNode *firstNode(ThreadTree tree) {
    ThreadNode *node = tree;
    while (node->ltag == 0) {
        node = node->lchild;
    }
    return node;
}

//求中序线索化二叉树中结点p在中序序列下的后继结点
ThreadNode *nextNode(ThreadNode *node) {
    if (node->rtag == 1) {
        return node->rchild;
    } else {
        return firstNode(node->rchild);
    }
}

//求中序线索化二叉树中的中序遍历算法
void inOrder(ThreadTree tree) {
    for (ThreadNode *node = firstNode(tree); node != NULL; node = nextNode(node)) {

        visit(node);
    }
    cout<<endl;
}